package com.future;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.lang.*;
import java.util.*;

/**
 * Description: 大厂刷题班第四节课 Code08_TheSkylineProblem
 * 城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。
 * <p>
 * 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
 * <p>
 * lefti 是第 i 座建筑物左边缘的 x 坐标。
 * righti 是第 i 座建筑物右边缘的 x 坐标。
 * heighti 是第 i 座建筑物的高度。
 * 你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。
 * <p>
 * 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。
 * 关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
 * <p>
 * 注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；
 * 三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/the-skyline-problem
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/26:9:46
 */
public class Solution_218 {

    public static void main(String[] args) {
/*
        Map<Integer, Integer> map = new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        map.put(1, 100);
        map.put(3, 100);
        map.put(2, 100);
        map.put(-10, 100);

        for (Map.Entry<Integer, Integer> m : map.entrySet()) {
            System.out.println(m.getKey() + ":" + m.getValue());
        }*/
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
        buildings = new int[][]{{0, 2, 3}, {1, 5, 3}};
        buildings = new int[][]{{4, 9, 10}, {4, 9, 15}, {4, 9, 12}, {10, 12, 10}, {10, 12, 8}};
        List<List<Integer>> ans = getSkyline(buildings);
        for (int i = 0; i < ans.size(); i++) {
            System.out.println(ans.get(i));
        }
    }

    /**
     * 思路：
     * eg：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
     * 1、遍历数组建立有下标和高度的对象Building，放到buildingList数组
     * 如[2,9,10]，有两个对象
     * Building:{position=2,isBeginPosition=true,height=10}
     * Building:{position=9,isBeginPosition=false,height=10}
     * ...
     * 2、对数组buildingList排序
     * 2.1 注意当有同一个起点是，height大的放前面！
     * 2.2 注意当有同一个终点是，height小的放前面！
     * 3、创建treeMap对象，把list中排好序的数据依次放入
     * 3.1 key是Building的height,value是height出现的频次
     * 3.2 put后，需要把treeMap中对大的key拿出来作为高度变化点放到link数组中
     * 4、遍历link(link的长度跟buildingList一样)
     * 4.1 同一个下标下，buildingList的position对应的高度就是link的height组成一个节点
     * 4.2 把相邻一样高度的去掉只保留第一个就可以了，放到一个数组里，最终返回
     *
     * @param buildings
     * @return
     */
    public static List<List<Integer>> getSkyline(int[][] buildings) {
        if (buildings == null || buildings.length == 0) {
            return new ArrayList<>();
        }
        int N = buildings.length;
        List<Building> buildingList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            buildingList.add(new Building(buildings[i][0], true, buildings[i][2]));
            buildingList.add(new Building(buildings[i][1], false, buildings[i][2]));
        }
        buildingList.sort(new Comparator<Building>() {
            @Override
            public int compare(Building o1, Building o2) {
                /**
                 * 重点
                 */
                int i = o1.position - o2.position;
                if (i == 0) {
                    /**
                     * 当开始或者结束节点一样时
                     */
                    boolean b = o1.isBeginPosition == o2.isBeginPosition;
                    if (b) {
                        /**
                         * 当开始或者结束节点一样时
                         */
                        b = o1.isBeginPosition;
                        if (b) {
                            // 开始节点一样，则高度大的排在前面（高会覆盖低的），否则出问题
                            // eg {{4, 9, 10}, {4, 9, 15}, {4, 9, 12}, {10, 12, 10}, {10, 12, 8}}
                            return o2.height - o1.height;
                        } else {
                            // 结束节点一样时，高度小的排前面，否则出问题
                            // eg [[1,2,1],[1,2,2],[1,2,3]]
                            return o1.height - o2.height;
                        }
                    } else {
                        return o1.isBeginPosition ? -1 : 1;
                    }
                }
                return o1.position - o2.position;
            }
        });
        List<Integer> link = new LinkedList<>();
        /**
         * key：height,value：times
         * key放高度，value是key的频次
         */
        Map<Integer, Integer> treeMap = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < buildingList.size(); i++) {
            Building obj = buildingList.get(i);
            boolean isBeginPosition = obj.isBeginPosition;
            int height = obj.height;
            if (isBeginPosition) {
                // 开始节点
                if (treeMap.containsKey(height)) {
                    // 存在就+1,为了防止有同一个启动的多个楼，需要判断是否包含
                    treeMap.put(height, treeMap.get(height) + 1);
                } else {
                    // 不存在就add
                    treeMap.put(height, 1);
                }
            } else {
                // 结束节点
                int time = treeMap.get(height) - 1;
                if (time == 0) {
                    // 当频次减少为0时，移除
                    treeMap.remove(height);
                } else {

                    treeMap.put(height, time);
                }
            }
            int max = 0;
            for (Map.Entry<Integer, Integer> m : treeMap.entrySet()) {
                max = m.getKey();
                break;
            }
            link.add(max);
        }
        List<List<Integer>> ans = new ArrayList<>();
        int prHeight = 0;
        for (int i = 0; i < 2 * N; i++) {
            int height = link.get(i);
            int position = buildingList.get(i).position;
            if (prHeight == height) {
                continue;
            }
            ans.add(new ArrayList<Integer>() {{
                add(position);
                add(height);
            }});
            prHeight = height;
        }
        return ans;
    }

    /**
     * 一个建筑的对象
     * eg {1,4,10}
     * 表示为
     * Buiding{1,true,10}
     * Buiding{4,false,10}
     */
    private static class Building {
        // 建筑位置
        public int position;

        // 是否是开始位置
        public boolean isBeginPosition;

        // 建筑高度
        public int height;

        public Building(int position, boolean isBeginPosition, int height) {
            this.position = position;
            this.isBeginPosition = isBeginPosition;
            this.height = height;
        }

        @Override
        public String toString() {
            return "Building{" +
                    "position=" + position +
                    ", isBeginPosition=" + isBeginPosition +
                    ", height=" + height +
                    '}';
        }
    }

}
